public class Solution {
    /**
     * 双指针
     */
    private class DoublePointer {
        /* package */ ListNode former;
        /* package */ ListNode later;
    }

    /**
     * 找出单向链表中倒数第k个节点。返回该节点的值
     */
    public int kthToLast(ListNode head, int k) {
        if (head == null) {
            System.out.println("head is NULL");
            return -1;
        }
        if (k <= 0) {
            System.out.println("k is less than or equal to 0");
            return -1;
        }

        DoublePointer doublePointer = new DoublePointer();
        doublePointer.former = head;
        boolean res = moveFormer(doublePointer, k);
        if (!res) {
            System.out.println("k exceeds the size of the list");
            return -1;
        }
        doublePointer.later = head;
        res = moveLater(doublePointer);
        if (!res) {
            return -1;
        }
        return doublePointer.later.val;
    }

    private ListNode moveLater(ListNode former, ListNode later) {
        for (int i = 0; former != null; former = former.next, later = later.next, i++) {
        }
        return later;
    }

    private boolean moveLater(DoublePointer doublePointer) {
        ListNode former = doublePointer.former;
        ListNode later = doublePointer.later;
        for (int i = 0; former != null; former = former.next, later = later.next, i++) {
        }
        doublePointer.former = former;
        doublePointer.later = later;
        return doublePointer.later != null;
    }

    private boolean moveFormer(DoublePointer doublePointer, int k) {
        ListNode former = doublePointer.former;
        int i = 0;
        for (; former != null && i < k; former = former.next, i++) {
        }
        doublePointer.former = former;
        return k <= i;
    }
}
